package book_mianshizhinan.test1_7;

import java.util.LinkedList;

public class NewMethod {

	public static void main(String[] args) {

		int[] arr = { 4, 3, 5, 4, 3, 3, 6, 7 };
		int[] result = getResult(arr, 3);
		for (int i = 0; i < result.length; i++) {
			System.out.print(result[i] + "  ");
		}

	}

	public static int[] getResult(int[] arr, int w) {
		int[] result = new int[arr.length - w + 1];
		LinkedList<Integer> qmax = new LinkedList<Integer>();

		/**
		 * 由于当前正在插入的值肯定和当前查找的窗口最大值有关，所以根据这个值， 排除所有比他小的值。 最后弹出过期值，确定没过期的最大值（队头）
		 */
		for (int i = 0; i < arr.length; i++) {
			int tmp = arr[i];

			while (!qmax.isEmpty() && tmp >= arr[qmax.peekLast()]) {
				qmax.pollLast();
			}
			qmax.addLast(i);

			if ((qmax.peekLast() - qmax.peekFirst()) == w) {
				qmax.pollFirst();
			}
			if (i >= w - 1) {
				result[i - w + 1] = arr[qmax.peekFirst()];
			}
		}

		return result;

	}

}
